package fireway;

import java.util.NoSuchElementException;

/**
 * 优先级队列
 * 2018年 04月 11日 星期三
 */
public class PriorityQueue {
    // Number of items in the queue
    private int mSize;

    // The queued items
    private long[] mItems;

    private static final long NULL_Element = 0L;

    public PriorityQueue(int initialCapacity) {
        mItems = new long[initialCapacity];
        mSize = 0;
    }

    public boolean add(long e) {
        if (isFull()) {
            throw new IllegalStateException("Queue full");
        } else {
            insert2(e);
            return true;
        }
    }

    public boolean offer(long e) {
        if (isFull()) {
            System.out.println("Queue full");
            return false;
        } else {
            insert2(e);
            return true;
        }
    }

    public long poll() {
        if (isEmpty()) {
            System.out.println("Queue empty");
            return NULL_Element;
        } else {
            return extract();
        }
    }

    public long remove() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue empty");
        } else {
            return extract();
        }
    }

    /**
     * 获取但不移除此队列的头
     */
    public long peek() {
        if (isEmpty()) {
            return NULL_Element;
        }
        return mItems[mSize - 1];
    }

    public boolean isEmpty() {
        return 0 == mSize;
    }

    public boolean isFull() {
        return mItems.length == mSize;
    }

    public int size() {
        return mSize;
    }

    private void insert(long e) {
        if (0 == mSize) {
            mItems[mSize++] = e;
        } else {
            int i = mSize - 1;
            for (; i >= 0; i--) {
                if (e > mItems[i]) {
                    mItems[i + 1] = mItems[i];
                } else {
                    break;
                }
            }
            mItems[i + 1] = e;
            mSize++;
        }
    }

    private void insert2(long e) {
        if (0 == mSize) {
            mItems[mSize++] = e;
        } else {
            int i = mSize - 1;
            for (; i >= 0; i--) {
                if (e < mItems[i]) {
                    break;
                }
            }

            for (int j = mSize; j > i + 1; j--) {
                mItems[j] = mItems[j - 1];
            }

            mItems[i + 1] = e;
            mSize++;
        }
    }

    private long extract() {
        long ret = mItems[mSize - 1];
        mSize--;
        return ret;
    }
}
